package util;

public class HeapSort {

	/**
	 * Standard heapsort.
	 * @param a an array of Comparable items.
	 */
	public static void HeapSort( Comparable [ ] a )
	{
	    for( int i = a.length / 2; i >= 0; i-- )  /* buildHeap */
	        percDown( a, i, a.length );
	    for( int i = a.length - 1; i > 0; i-- )
	    {
	        swapReferences( a, 0, i );            /* deleteMax */
	        percDown( a, 0, i );
	    }
	}
	
	/**
	 * Internal method for heapsort.
	 * @param i the index of an item in the heap.
	 * @return the index of the left child.
	 */
	private static int leftChild( int i )
	{
	    return 2 * i + 1;
	}
	
	/**
	 * Internal method for heapsort that is used in
	 * deleteMax and buildHeap.
	 * @param a an array of Comparable items.
	 * @index i the position from which to percolate down.
	 * @int n the logical size of the binary heap.
	 */
	private static void percDown( Comparable [ ] a, int i, int n )
	{
	    int child;
	    Comparable tmp;
	
	    for( tmp = a[ i ]; leftChild( i ) < n; i = child )
	    {
	        child = leftChild( i );
	        if( child != n - 1 && a[ child ].compareTo( a[ child + 1 ] ) < 0 )
	            child++;
	        if( tmp.compareTo( a[ child ] ) < 0 )
	            a[ i ] = a[ child ];
	        else
	            break;
	    }
	    a[ i ] = tmp;
	}
	
	
	/**
	 * Method to swap to elements in an array.
	 * @param a an array of objects.
	 * @param index1 the index of the first object.
	 * @param index2 the index of the second object.
	 */
	public static final void swapReferences( Object [ ] a, int index1, int index2 )
	{
	    Object tmp = a[ index1 ];
	    a[ index1 ] = a[ index2 ];
	    a[ index2 ] = tmp;
	}
}
